SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Costas array</title>

</head>

Costas array

</h1>

</header>

In mathematics, a Costas array can be regarded <a href="Geometry" title="Geometry">geometrically</a> as a set of n points, each at the center of a <a href="Square" title="Square">square</a> in an n×n <a href="Square_tiling" title="Square tiling">square tiling</a> such that each row or column contains only one point, and all of the n(n − 1)/2 <a href="Displacement_(vector)" class="mw-redirect" title="Displacement (vector)">displacement</a> <a href="Euclidean_vector" title="Euclidean vector">vectors</a> between each pair of dots are distinct. This results in an ideal "thumbtack" auto-<a href="Ambiguity_function" title="Ambiguity function">ambiguity function</a>, making the arrays useful in applications such as <a href="Sonar" title="Sonar">sonar</a> and <a href="Radar" title="Radar">radar</a>. Costas arrays can be regarded as two-dimensional cousins of the one-dimensional <a href="Golomb_ruler" title="Golomb ruler">Golomb ruler</a> construction, and, as well as being of mathematical interest, have similar applications in <a href="Experimental_design" class="mw-redirect" title="Experimental design">experimental design</a> and <a href="Phased_array" title="Phased array">phased array</a> radar engineering.

Costas arrays are named after <a href="John_P._Costas_(engineer)" title="John P. Costas (engineer)">John P. Costas</a>, who first wrote about them in a 1965 technical report. Independently, <a href="Edgar_Gilbert" title="Edgar Gilbert">Edgar Gilbert</a> also wrote about them in the same year, publishing what is now known as the logarithmic Welch method of constructing Costas arrays.<a href="#cite_note-1">[1]</a>

The general enumeration of Costas arrays is an open problem in computer science and finding an algorithm that can solve it in polynomial time is an open research question.

<div class="mw-heading mw-heading2"><h2 id="Numerical_representation">Numerical representation</h2></div>

A Costas array may be represented numerically as an n×n array of numbers, where each entry is either 1, for a point, or 0, for the absence of a point. When interpreted as <a href="Logical_matrix" title="Logical matrix">binary matrices</a>, these arrays of numbers have the property that, since each row and column has the constraint that it only has one point on it, they are therefore also <a href="Permutation_matrix" title="Permutation matrix">permutation matrices</a>. Thus, the Costas arrays for any given n are a subset of the permutation matrices of order n.

Arrays are usually described as a series of indices specifying the column for any row. Since it is given that any column has only one point, it is possible to represent an array one-dimensionally. For instance, the following is a valid Costas array of order N = 4:

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}</annotation>

</semantics>

</math><img src="./b374bab81322214427c5ebd8f205bad76f470bf9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:14.227ex; height:13.509ex;" alt="{\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}" loading="lazy">    or simply     <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}">

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}</annotation>

</semantics>

</math><img src="./b7d18e3cd206e01bce580e0aee2cebe46ff6bfef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:14.227ex; height:13.509ex;" alt="{\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}" loading="lazy"></dd></dl>

There are dots at coordinates: (1,2), (2,1), (3,3), (4,4)

Since the x-coordinate increases linearly, we can write this in shorthand as the set of all y-coordinates. The position in the set would then be the x-coordinate. Observe: {2,1,3,4} would describe the aforementioned array. This defines a permutation. This makes it easy to communicate the arrays for a given order of N.

<div class="mw-heading mw-heading2"><h2 id="Known_arrays">Known arrays</h2></div>

Costas array counts are known for orders 1 through 29<a href="#cite_note-2">[2]</a> (sequence <a href="https://oeis.org/A008404" class="extiw external" title="oeis:A008404">A008404</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>):

<th scope="col" width="width:20em;">Order

</th>

<th scope="col" width="width:20em;">Number

</th></tr>

<tr>

<td>1

</td>

<td>1

</td></tr>

<tr>

<td>2

</td>

<td>2

</td></tr>

<tr>

<td>3

</td>

<td>4

</td></tr>

<tr>

<td>4

</td>

<td>12

</td></tr>

<tr>

<td>5

</td>

<td>40

</td></tr>

<tr>

<td>6

</td>

<td>116

</td></tr>

<tr>

<td>7

</td>

<td>200

</td></tr>

<tr>

<td>8

</td>

<td>444

</td></tr>

<tr>

<td>9

</td>

<td>760

</td></tr>

<tr>

<td>10

</td>

<td>2160

</td></tr>

<tr>

<td>11

</td>

<td>4368

</td></tr>

<tr>

<td>12

</td>

<td>7852

</td></tr>

<tr>

<td>13

</td>

<td>12828

</td></tr>

<tr>

<td>14

</td>

<td>17252

</td></tr>

<tr>

<td>15

</td>

<td>19612

</td></tr>

<tr>

<td>16

</td>

<td>21104

</td></tr>

<tr>

<td>17

</td>

<td>18276

</td></tr>

<tr>

<td>18

</td>

<td>15096

</td></tr>

<tr>

<td>19

</td>

<td>10240

</td></tr>

<tr>

<td>20

</td>

<td>6464

</td></tr>

<tr>

<td>21

</td>

<td>3536

</td></tr>

<tr>

<td>22

</td>

<td>2052

</td></tr>

<tr>

<td>23

</td>

<td>872

</td></tr>

<tr>

<td>24

</td>

<td>200

</td></tr>

<tr>

<td>25

</td>

<td>88

</td></tr>

<tr>

<td>26

</td>

<td>56

</td></tr>

<tr>

<td>27

</td>

<td>204

</td></tr>

<tr>

<td>28

</td>

<td>712

</td></tr>

<tr>

<td>29

</td>

<td>164

</td></tr>

</tbody></table>

Here are some known arrays:

N = 1

{1}

N = 2

{1,2} {2,1}

N = 3

{1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4

{1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}

N = 5

{1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6

{1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}

Enumeration of known Costas arrays to order 200,<a href="#cite_note-FOOTNOTEBeard2006-3">[3]</a> order 500<a href="#cite_note-FOOTNOTEBeard2008-4">[4]</a> and to order 1030<a href="#cite_note-5">[5]</a> are available. Although these lists and databases of these Costas arrays are likely near complete, other Costas arrays with orders above 29 that are not in these lists may exist. In general, the currently best known upper bound on the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(n)}</annotation>

</semantics>

</math><img src="./a942b876da9e5ee96248dfb6ab52ae643c3aa3ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.97ex; height:2.843ex;" alt="{\displaystyle C(n)}" loading="lazy"> of Costas Arrays of order <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is of asymptotic form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(n)/n!\leq e^{-\Theta (n)}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(n)/n!\leq e^{-\Theta (n)}}</annotation>

</semantics>

</math><img src="./9d1b59cfb494377317be5e949a1058e9bf6ff917.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.411ex; height:3.343ex;" alt="{\displaystyle C(n)/n!\leq e^{-\Theta (n)}}" loading="lazy">.<a href="#cite_note-FOOTNOTEWarnkeCorrellSwanson2023-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Constructions">Constructions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Welch">Welch</h3></div>

A Welch–Costas array, or just Welch array, is a Costas array generated using the following method, first discovered by <a href="Edgar_Gilbert" title="Edgar Gilbert">Edgar Gilbert</a> in 1965 and rediscovered in 1982 by <a href="Lloyd_R._Welch" title="Lloyd R. Welch">Lloyd R. Welch</a>.

The Welch–Costas array is constructed by taking a <a href="Primitive_root_modulo_n" title="Primitive root modulo n">primitive root</a> g of a <a href="Prime_number" title="Prime number">prime number</a> p and defining the array A by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i,j}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i,j}=1}</annotation>

</semantics>

</math><img src="./f99ee84b748273a6535235724a431c2f17ae0df8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.939ex; height:2.843ex;" alt="{\displaystyle A_{i,j}=1}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\equiv g^{i}{\bmod {p}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\equiv g^{i}{\bmod {p}}}</annotation>

</semantics>

</math><img src="./40d4105d8ca52b144498f13aebf3ab4da23fda0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.852ex; height:3.009ex;" alt="{\displaystyle j\equiv g^{i}{\bmod {p}}}" loading="lazy">, otherwise 0. The result is a Costas array of size p − 1.

Example:

3 is a primitive element modulo 5.

Therefore, [3 4 2 1] is a Costas permutation. More specifically, this is an exponential Welch array. The transposition of the array is a logarithmic Welch array.

The number of Welch–Costas arrays which exist for a given size depends on the <a href="Euler's_totient_function" title="Euler's totient function">totient function</a>.

<div class="mw-heading mw-heading3"><h3 id="Lempel–Golomb">Lempel–Golomb</h3></div>

The Lempel–Golomb construction takes α and β to be <a href="Primitive_element_(finite_field)" title="Primitive element (finite field)">primitive elements</a> of the <a href="Finite_field" title="Finite field">finite field</a> GF(q) and similarly defines <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i,j}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i,j}=1}</annotation>

</semantics>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha ^{i}+\beta ^{j}=1}</annotation>

</semantics>

</math><img src="./3a81eb61492cdd1967ba207ac7b63b95b864dd27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.635ex; height:3.009ex;" alt="{\displaystyle \alpha ^{i}+\beta ^{j}=1}" loading="lazy">, otherwise 0. The result is a Costas array of size q − 2. If α + β = 1 then the first row and column may be deleted to form another Costas array of size q − 3: such a pair of primitive elements exists for every prime power q>2.

<div class="mw-heading mw-heading3"><h3 id="Extensions_by_Taylor,_Lempel,_and_Golomb">Extensions by Taylor, Lempel, and Golomb</h3></div>

Generation of new Costas arrays by adding or subtracting a row/column or two with a 1 or a pair of 1's in a corner were published in a paper focused on generation methods<a href="#cite_note-FOOTNOTEGolomb1984-7">[7]</a> and in Golomb and Taylor's landmark 1984 paper.<a href="#cite_note-FOOTNOTEGolombTaylor1984-8">[8]</a>

More sophisticated methods of generating new Costas arrays by deleting rows and columns of existing Costas arrays that were generated by the Welch, Lempel or Golomb generators were published in 1992.<a href="#cite_note-FOOTNOTEGolomb1992-9">[9]</a> There is no upper limit on the order for which these generators will produce Costas arrays.

<div class="mw-heading mw-heading3"><h3 id="Other_methods">Other methods</h3></div>

Two methods that found Costas arrays up to order 52 using more complicated methods of adding or deleting rows and columns were published in 2004<a href="#cite_note-FOOTNOTERickard2004-10">[10]</a> and 2007.<a href="#cite_note-FOOTNOTEBeardRussoEricksonMonteleone2007-11">[11]</a>

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

Costas arrays on a <a href="Hexagonal_lattice" title="Hexagonal lattice">hexagonal lattice</a> are known as honeycomb arrays. It has been shown that there are only finitely many such arrays, which must have an odd number of elements, arranged in the shape of a hexagon. Currently, 12 such arrays (up to symmetry) are known, which has been conjectured to be the total number.<a href="#cite_note-12">[12]</a>

<ul><li><a href="Permutation" title="Permutation">Permutation</a></li>

<li><a href="Dihedral_group" title="Dihedral group">Dihedral group</a></li>

<li><a href="Combinatorial_design" title="Combinatorial design">Combinatorial design</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFCostas1965">Costas (1965)</a>; <a href="#CITEREFGilbert1965">Gilbert (1965)</a>; <a rel="nofollow" class="external text" href="http://nanoexplanations.wordpress.com/2011/10/09/an-independent-discovery-of-costas-arrays/">An independent discovery of Costas arrays</a>, Aaron Sterling, October 9, 2011.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="#CITEREFBeard2006">Beard (2006)</a>; <a href="#CITEREFDrakakisRickardBeardCaballero2008">Drakakis et al. (2008)</a>; <a href="#CITEREFDrakakisIorioRickard2011">Drakakis, Iorio & Rickard (2011)</a>; <a href="#CITEREFDrakakisIorioRickardWalsh2011">Drakakis et al. (2011)</a>

</li>

<li id="cite_note-FOOTNOTEBeard2006-3"><a href="#cite_ref-FOOTNOTEBeard2006_3-0">^</a> <a href="#CITEREFBeard2006">Beard (2006)</a>.

</li>

<li id="cite_note-FOOTNOTEBeard2008-4"><a href="#cite_ref-FOOTNOTEBeard2008_4-0">^</a> <a href="#CITEREFBeard2008">Beard (2008)</a>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="#CITEREFBeard2017">Beard (2017)</a>; <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBeard" class="citation cs2">Beard, James K., <a rel="nofollow" class="external text" href="http://jameskbeard.com/jameskbeard/Files.html#CostasArrays">Files for Download: Costas Arrays</a>, retrieved 2020-04-20</cite>

</li>

<li id="cite_note-FOOTNOTEWarnkeCorrellSwanson2023-6"><a href="#cite_ref-FOOTNOTEWarnkeCorrellSwanson2023_6-0">^</a> <a href="#CITEREFWarnkeCorrellSwanson2023">Warnke, Correll & Swanson (2023)</a>.

</li>

<li id="cite_note-FOOTNOTEGolomb1984-7"><a href="#cite_ref-FOOTNOTEGolomb1984_7-0">^</a> <a href="#CITEREFGolomb1984">Golomb (1984)</a>.

</li>

<li id="cite_note-FOOTNOTEGolombTaylor1984-8"><a href="#cite_ref-FOOTNOTEGolombTaylor1984_8-0">^</a> <a href="#CITEREFGolombTaylor1984">Golomb & Taylor (1984)</a>.

</li>

<li id="cite_note-FOOTNOTEGolomb1992-9"><a href="#cite_ref-FOOTNOTEGolomb1992_9-0">^</a> <a href="#CITEREFGolomb1992">Golomb (1992)</a>.

</li>

<li id="cite_note-FOOTNOTERickard2004-10"><a href="#cite_ref-FOOTNOTERickard2004_10-0">^</a> <a href="#CITEREFRickard2004">Rickard (2004)</a>.

</li>

<li id="cite_note-FOOTNOTEBeardRussoEricksonMonteleone2007-11"><a href="#cite_ref-FOOTNOTEBeardRussoEricksonMonteleone2007_11-0">^</a> <a href="#CITEREFBeardRussoEricksonMonteleone2007">Beard et al. (2007)</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBlackburnPanouiPatersonStinson2010" class="citation journal cs2">Blackburn, Simon R.; Panoui, Anastasia; Paterson, Maura B.; Stinson, Douglas R. (2010-12-10), <a rel="nofollow" class="external text" href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r172">"Honeycomb Arrays"</a>, The Electronic Journal of Combinatorics, 17: R172, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F444">10.37236/444</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1077-8926">1077-8926</a></cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBarkerDrakakisRickard2009" class="citation cs2">Barker, L.; Drakakis, K.; Rickard, S. (2009), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120425053202/http://eeme.ucd.ie/~kdrakaka/work/publications/020.On_The_Complexity_Of_The_Verification_Of_The_Costas_Property.pdf">"On the complexity of the verification of the Costas property"</a> (PDF), Proceedings of the IEEE, 97 (3): 586–593, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2008.2011947">10.1109/JPROC.2008.2011947</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29776660">29776660</a>, archived from <a rel="nofollow" class="external text" href="http://eeme.ucd.ie/~kdrakaka/work/publications/020.On_The_Complexity_Of_The_Verification_Of_The_Costas_Property.pdf">the original</a> (PDF) on 2012-04-25, retrieved 2011-10-10</cite>.</li>

<li><cite id="CITEREFBeard2006" class="citation cs2">Beard, James (March 2006), "Generating Costas Arrays to Order 200", 2006 40th Annual Conference on Information Sciences and Systems, IEEE, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fciss.2006.286635">10.1109/ciss.2006.286635</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2241386">2241386</a></cite>.</li>

<li><cite id="CITEREFBeard2008" class="citation cs2">Beard, James K. (March 2008), "Costas array generator polynomials in finite fields", 2008 42nd Annual Conference on Information Sciences and Systems, IEEE, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fciss.2008.4558709">10.1109/ciss.2008.4558709</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:614347">614347</a></cite>.</li>

<li><cite id="CITEREFBeard2017" class="citation cs2">Beard, James K. (2017), <a rel="nofollow" class="external text" href="https://ieee-dataport.org/open-access/costas-arrays-and-enumeration-order-1030">Costas arrays and enumeration to order 1030</a>, IEEE Dataport, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.21227%2FH21P42">10.21227/H21P42</a></cite>.</li>

<li><cite id="CITEREFBeardRussoEricksonMonteleone2004" class="citation cs2">Beard, J.; Russo, J.; Erickson, K.; Monteleone, M.; Wright, M. (2004), "Combinatoric collaboration on Costas arrays and radar applications", <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120425053202/http://www.costasarrays.org/costasrefs/beard04combinatoric.pdf">IEEE Radar Conference, Philadelphia, Pennsylvania</a> (PDF), pp. 260–265, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FNRC.2004.1316432">10.1109/NRC.2004.1316432</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7733481">7733481</a>, archived from <a rel="nofollow" class="external text" href="http://www.costasarrays.org/costasrefs/beard04combinatoric.pdf">the original</a> (PDF) on 2012-04-25, retrieved 2011-10-10</cite>.</li>

<li><cite id="CITEREFBeardRussoEricksonMonteleone2007" class="citation cs2">Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (April 2007), <a rel="nofollow" class="external text" href="https://zenodo.org/record/893374">"Costas array generation and search methodology"</a>, IEEE Transactions on Aerospace and Electronic Systems, 43 (2): 522–538, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftaes.2007.4285351">10.1109/taes.2007.4285351</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:32271456">32271456</a></cite>.</li>

<li><cite id="CITEREFCostas1965" class="citation cs2"><a href="John_P._Costas_(engineer)" title="John P. Costas (engineer)">Costas, J. P.</a> (1965), Medium constraints on sonar design and performance, Class 1 Report R65EMH33, G.E. Corporation</cite></li>

<li><cite id="CITEREFCostas1984" class="citation cs2"><a href="John_P._Costas_(engineer)" title="John P. Costas (engineer)">Costas, J. P.</a> (1984), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110930054819/http://www.costasarrays.org/costasrefs/costas84study.pdf">"A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties"</a> (PDF), Proceedings of the IEEE, 72 (8): 996–1009, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FPROC.1984.12967">10.1109/PROC.1984.12967</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2742217">2742217</a>, archived from <a rel="nofollow" class="external text" href="http://costasarrays.org/costasrefs/costas84study.pdf">the original</a> (PDF) on 2011-09-30, retrieved 2011-10-10</cite>.</li>

<li><cite id="CITEREFDrakakisRickardBeardCaballero2008" class="citation cs2">Drakakis, Konstantinos; Rickard, Scott; Beard, James K.; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (October 2008), "Results of the Enumeration of Costas Arrays of Order 27", IEEE Transactions on Information Theory, 54 (10): 4684–4687, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftit.2008.928979">10.1109/tit.2008.928979</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2262%2F59260">2262/59260</a></cite>.</li>

<li><cite id="CITEREFDrakakisIorioRickard2011" class="citation cs2">Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott (2011), "The enumeration of Costas arrays of order 28 and its consequences", Advances in Mathematics of Communications</cite></li>

<li><cite id="CITEREFDrakakisIorioRickardWalsh2011" class="citation cs2">Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (August 2011), "Results of the enumeration of Costas arrays of order 29", Advances in Mathematics of Communications, 5 (3): 547–553, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3934%2Famc.2011.5.547">10.3934/amc.2011.5.547</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2262%2F59260">2262/59260</a></cite>.</li>

<li><cite id="CITEREFGilbert1965" class="citation cs2"><a href="Edgar_Gilbert" title="Edgar Gilbert">Gilbert, E. N.</a> (1965), "Latin squares which contain no repeated digrams", SIAM Review, 7 (2): 189–198, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1007035">10.1137/1007035</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0179095">0179095</a></cite>.</li>

<li><cite id="CITEREFGolomb1984" class="citation cs2"><a href="Solomon_W._Golomb" title="Solomon W. Golomb">Golomb, Solomon W.</a> (1984), "Algebraic constructions for Costas arrays", Journal of Combinatorial Theory, Series A, 37 (1): 13–21, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2884%2990015-3">10.1016/0097-3165(84)90015-3</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0749508">0749508</a></cite>.</li>

<li><cite id="CITEREFGolomb1992" class="citation cs2"><a href="Solomon_W._Golomb" title="Solomon W. Golomb">Golomb, Solomon W.</a> (1992), "The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{4}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{4}}</annotation>

</semantics>

</math><img src="./83a8e4649fd334cf176ee7badff8eb949ecd3670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{4}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{4}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{4}}</annotation>

</semantics>

</math><img src="./149de5cbc9bd78a60484b9c011a9020531255118.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{4}}" loading="lazy"> constructions for Costas arrays", IEEE Transactions on Information Theory, 38 (4): 1404–1406, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.144726">10.1109/18.144726</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1168761">1168761</a></cite></li>

<li><cite id="CITEREFGolombTaylor1984" class="citation cs2"><a href="Solomon_W._Golomb" title="Solomon W. Golomb">Golomb, S. W.</a>; Taylor, H. (1984), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110930054835/http://www.costasarrays.org/costasrefs/golomb84constructions.pdf">"Construction and properties of Costas arrays"</a> (PDF), Proceedings of the IEEE, 72 (9): 1143–1163, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FPROC.1984.12994">10.1109/PROC.1984.12994</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:39718506">39718506</a>, archived from <a rel="nofollow" class="external text" href="http://www.costasarrays.org/costasrefs/golomb84constructions.pdf">the original</a> (PDF) on 2011-09-30, retrieved 2011-10-10</cite>.</li>

<li><cite id="CITEREFGuy2004" class="citation cs2"><a href="Richard_K._Guy" title="Richard K. Guy">Guy, Richard K.</a> (2004), "Sections C18 and F9", Unsolved Problems in Number Theory (3rd ed.), <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-20860-7</bdi></cite>.</li>

<li><cite id="CITEREFMoreno1999" class="citation cs2">Moreno, Oscar (1999), "Survey of results on signal patterns for locating one or multiple targets", in Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (eds.), Difference Sets, Sequences and Their Correlation Properties, NATO Advanced Science Institutes Series, vol. 542, Kluwer, p. 353, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7923-5958-5</bdi></cite>.</li>

<li><cite id="CITEREFRickard2004" class="citation cs2">Rickard, Scott (2004), "Searching for Costas Arrays using Periodicity Properties", IMA International Conference on Mathematics in Signal Processing</cite>.</li>

<li><cite id="CITEREFWarnkeCorrellSwanson2023" class="citation cs2">Warnke, Lutz; Correll, Bill; Swanson, Christopher (2023), "The density of Costas arrays decays exponentially", IEEE Transactions on Information Theory, 69 (1): 575–581, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2022.3202507">10.1109/TIT.2022.3202507</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4544975">4544975</a></cite>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a href="MacTech" title="MacTech">MacTech</a> 1999 Programmer's challenge: <a rel="nofollow" class="external text" href="http://www.mactech.com/progchallenge/9912Challenge.html">Costas arrays</a></li>

<li><a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">On-Line Encyclopedia of Integer Sequences</a>:

<ul><li>A008404: <a href="https://oeis.org/A008404" class="extiw external" title="oeis:A008404">Number of Costas arrays of order n, counting rotations and flips as distinct.</a></li>

<li>A001441: <a href="https://oeis.org/A001441" class="extiw external" title="oeis:A001441">Number of inequivalent Costas arrays of order n under dihedral group.</a></li></ul></li>

<li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Costas_array">"Costas array"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-29" href="https://en.wikipedia.org/wiki/?title=Costas_array&oldid=1266023669">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>